package trees;

public class SearchInsert {
    public int searchInsert(int[] nums, int target) {
        if (nums == null || nums.length == 0 || target == 0) {
            return 0;
        }

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                return i;
            }

            if (target < nums[i]) {
                return i - 1 > 0 ? i : 0;
            }

            if (i + 1 == nums.length) {
                return nums.length;
            }

            if (target > nums[i] && target <= nums[i + 1]) {
                return i + 1;
            }
        }

        return 0;
    }

    public int searchInsert2(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return 0;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{2, 5};
        int target = 1;
        SearchInsert insert = new SearchInsert();
        System.out.println(insert.searchInsert(nums, target));
    }
}
